package rekursion;

public class Solitaire{
  /* Backtracking am Beispiel von Solitaire */
  static final int S=15; //Stein
  static final int _=-1; //Rand
  static final int O=0;  //freier Platz
  static int[][] felder={//Alle Steine müssen mit _ begrenzt sein!
    {_,_,_,_,_,_},      
    {_,_,_,S,S,S,_},    
    {_,_,_,S,S,S,_,_},  
    {_,S,S,S,S,S,S,S,_},
    {_,S,S,S,O,S,S,S,_},
    {_,S,S,S,S,S,S,S,_},
    {_,_,_,S,S,S,_,_},  
    {_,_,_,S,S,S,_},    
    {_,_,_,_,_,_}
  };//der erste Index ist die y-Richtung!
  static int xEnd=-1, yEnd=4;//gewünschte Lage des letzten Steins -1, -1 falls egal
  static Zug[] zuege;//Definition siehe Ende der Datei
  static int nr; //aktueller Index im Array zuege
  static int anz;//Anzahl der bisher gefundenen Lösungen

  public static void main(String[] args){
    int steine=0, freie=0;
    nr=-1; anz=0;
    for(int y=1; y<felder.length-1; y++)
      for(int x=1; x<felder[y].length-1; x++){
        if(felder[y][x]==S) steine++;
        if(felder[y][x]==O) freie++;
      }
    zuege=new Zug[steine-1];
    for(int i=0; i<steine-1; i++) zuege[i]=new Zug();
    System.out.println(
      "In allen Angaben ist x=0 ganz links und y=0 ganz oben.\n"+
      "(0,0) kommt nie vor, weil am Rand kein Stein sein darf.\n"+
      "Der Zug von (2,3) nach (2,5) wird dargestellt als (2,3,v)\n"+
      "Die möglichen Zeichen sind <^>v für links, rauf, rechts, runter\n"
    );
    System.out.println("Es gibt "+steine+" Steine und "+freie+" Löcher.");
    testeAlle();
  }

  public static void testeAlle(){
    for(int y=felder.length-1; y>=0; --y)
      for(int x=felder[y].length-1; x>=0; --x)
        if(felder[y][x]==O){
          nr++;
          reinRaus(x, 0, y, -1, 'v');
          reinRaus(x, -1, y, 0, '>');
          reinRaus(x, 0, y, +1, '^');
          reinRaus(x, +1, y, 0, '<');
          nr--;
        }
  }

  public static void reinRaus(int x, int dx, int y, int dy, char c){
    if(felder[y+dy][x+dx]==S && felder[y+2*dy][x+2*dx]==S){
      felder[y][x]=S; felder[y+dy][x+dx]=felder[y+2*dy][x+2*dx]=O;
      merkeZug(x+2*dx, y+2*dy, c);
      if(nr<zuege.length-1)
        testeAlle();
      else if(xEnd<0 || yEnd<0 || (y==yEnd && x==xEnd)){
          System.out.println("Lösung gefunden:");
          for(int i=0; i<zuege.length; i++)
            System.out.print("("+zuege[i].x+","+zuege[i].y+","+zuege[i].d+")\t");
          System.out.println();
        }
      felder[y][x]=O; felder[y+dy][x+dx]=felder[y+2*dy][x+2*dx]=S;
    }
  }

  private static int max=-1;
  public static void merkeZug(int x, int y, char d){
    zuege[nr].y=y;
    zuege[nr].x=x;
    zuege[nr].d=d;
    if(nr>max) System.out.print((max=nr)+" ");
    if(nr>=zuege.length-1 && (xEnd<0 || yEnd<0 || (y==yEnd && x==xEnd))){
      System.out.println(++anz+". Lösung gefunden:");
      for(int i=0; i<zuege.length; i++)
        System.out.print("("+zuege[i].x+","+zuege[i].y+","+zuege[i].d+")\t");
      System.out.println();
    }
  }
}

class Zug{
  int x, y;
  char d;

  public Zug(int x, int y, char d){
    this.x=x;
    this.y=y;
    this.d=d;
  }

  public Zug(){}

  @Override
  public boolean equals(Object o){
    if(o instanceof Zug){
      Zug z=(Zug)o;
      return z.x==x && z.y==y && z.d==d;
    } else return false;
  }
}
